<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2543：[Ctsc2001]逻辑电路最优设计</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2001]逻辑电路最优设计</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2001]逻辑电路最优设计</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Ctsc2001]逻辑电路最优设计                </h1>
                <p>时间限制：1s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="text-indent: 24pt"><span style="font-size: 12pt">W</span><span style="font-size: 12pt">教授在</span><span style="font-size: 12pt">T</span><span style="font-size: 12pt">大学计算机系里开了一门&ldquo;数字逻辑&rdquo;课，主要讲授如何设计逻辑电路。这一天，</span><span style="font-size: 12pt">W</span><span style="font-size: 12pt">教授布置了一个实验：设计并实现一个</span><span style="font-size: 12pt">4</span><span style="font-size: 12pt">端输入、</span><span style="font-size: 12pt">4</span><span style="font-size: 12pt">端输出的逻辑译码电路。设计这样的电路原本并不困难，但是，教授给出了如下的要求：</span></div>
<div style="margin: 0cm 0cm 0pt 39pt; text-indent: -18pt"><span style="font-size: 12pt">1．</span><span style="font-size: 12pt">只允许使用</span><span style="font-size: 12pt">2</span><span style="font-size: 12pt">端输入、</span><span style="font-size: 12pt">1</span><span style="font-size: 12pt">端输出的门电路作为实现电路的组件，而且可用门电路的种类和数目都已给定；</span></div>
<div style="margin: 0cm 0cm 0pt 39pt; text-indent: -18pt"><span style="font-size: 12pt">2．</span><span style="font-size: 12pt">使用最少数目的门电路。</span></div>
<div style="margin: 0cm 0cm 0pt 21pt">&nbsp;</div>
<div style="text-indent: 24pt"><span style="font-size: 12pt">这两个要求难倒了全系的同学，于是，</span><span style="font-size: 12pt">Q</span><span style="font-size: 12pt">同学找到了正在参加</span><span style="font-size: 12pt">CTSC</span><span style="font-size: 12pt">（中国队选拔赛）的你，希望你能帮忙编写一个程序，自动找出符合要求的连接方式。</span></div>
<div style="text-indent: 24pt">&nbsp;</div>
<div style="text-indent: 24pt"><span style="font-size: 12pt">在数字逻辑中，所有信号都可以看作只有两个值：&ldquo;高电平&rdquo;和&ldquo;低电平&rdquo;，分别用&ldquo;</span><span style="font-size: 12pt">1</span><span style="font-size: 12pt">&rdquo;和&ldquo;</span><span style="font-size: 12pt">0</span><span style="font-size: 12pt">&rdquo;来表示。</span></div>
<div style="text-indent: 24pt"><span style="font-size: 12pt">一个门电路元件的特性由其输入</span><span style="font-size: 12pt">/</span><span style="font-size: 12pt">输出功能表唯一给出，所谓功能表，就是输入信号电平与输出信号电平之间的关系表。比如，&ldquo;与门&rdquo;的符号和功能表如下图所示：</span></div>
<div style="text-indent: 24pt"><span style="font-size: 12pt"><img height="190" width="522" alt="" src="../file/2543_0.jpg" /></span></div>
<p></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">上图中，如果&ldquo;与门&rdquo;的两个输入端</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">X</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Y</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">都是高电平&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;，则输出端</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">S</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">也是高电平&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;，否则，输出端</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">S</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是低电平&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">0</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">假定，本次实验提供的门电路都具有输入对称性，即交换两个输入端的信号，输出不变。但是，如果门电路的输入端悬空（即没有加输入信号），则输出无意义。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span lang="EN-US" style="font-size: 12pt"><o:p><font face="Times New Roman">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">在连接电路的过程中，一个门电路的输出端可以将信号送到其他多个元件的输入端；而门电路的一个输入端则只能接收来自一个输出端的信号。如下图所示：</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><o:wrapblock><v:shapetype id="_x0000_t202" coordsize="21600,21600" o:spt="202" path="m,l,21600r21600,l21600,xe"><v:stroke joinstyle="miter"></v:stroke><v:path gradientshapeok="t" o:connecttype="rect"></v:path></v:shapetype></o:wrapblock><img alt="" src="../file/2543_1.jpg" /><br clear="all" style="mso-ignore: vglayout" />
<span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">另外，规定信号必须单向传输，即一个门电路的输出不能直接或间接通过其他门电路回到同一门电路的输入端。如下图所示即为两种不允许的连接方式：</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><o:wrapblock><v:shapetype id="_x0000_t202" coordsize="21600,21600" o:spt="202" path="m,l,21600r21600,l21600,xe"><v:stroke joinstyle="miter"></v:stroke><v:path gradientshapeok="t" o:connecttype="rect"></v:path></v:shapetype><v:shape id="_x0000_s1026" type="#_x0000_t202" stroked="f" style="margin-top: 73pt; z-index: 1; left: 0px; margin-left: 45pt; width: 4in; text-indent: 0px; position: absolute; height: 70.2pt; text-align: left; mso-position-vertical-relative: page"><v:textbox style="mso-next-textbox: #_x0000_s1026"></v:textbox><w:wrap type="topAndBottom" anchory="page"></w:wrap></v:shape></o:wrapblock><img alt="" src="../file/2543_2.jpg" /><br clear="all" style="mso-ignore: vglayout" />
<span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">要求你设计的译码电路是一个有四个输入端和四个输出端的逻辑电路，该译码电路的输入和输出关系通过功能表给出，即给出每种输入组合下的四个输出端的情况。显然，一共有</span><span lang="EN-US" style="font-size: 12pt"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"> 2^4=16</span></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">种输入组合。比如，一个由前述&ldquo;与门&rdquo;构成的</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">2</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">输入，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">2</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">输出的简单译码电路如下图所示（其中，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">A1, A2</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是输入端，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Y1, Y2</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是输出端）：</span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><img alt="" src="../file/2543_3.jpg" /></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"></p></p><hr/><h3>输入格式</h3><p><p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">其中第一行为一个正整数</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">N,N&lt;=5</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，表示元件的种类数，其后有连续的</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">N</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行，每行描述一种元件。对正整数</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1&lt;=K&lt;=N<o:p></o:p></font></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">文件的第</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">K+1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行有四个以空格隔开的整数，依次为：</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Mk Y00 Y01 Y11<o:p></o:p></font></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">其中，正整数</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Mk</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示第</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">K</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">种元件的数目（</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">K</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">即这种元件的种类编号），所有元件的数目之和不会超过</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">10</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">（用于实验的经费并不充足）。</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Yij</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示两个输入端分别为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">i</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">j</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">时的输出，即</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Y00,Y01,Y11</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是三个非</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">0</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">即</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的数，分别表示在两个输入端均为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">0</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">；两个输入端一个为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">0</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">另一个为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">；以及两个输入端均为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的时候，该元件的输出。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">输入文件的第</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">N+2</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">到第</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">N+17</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行，表示需组成的集成电路的功能表，每行有</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">8</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个数，分别为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">0</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">或</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">。其中，前四个数依次对应四个输入端（编号为</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">～</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">4</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">）的信号，不存在两行的前四个数完全相同；而后面四个数则对应在各输入端信号为前四个数时，四个输出端依次应输出的信号。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p></p></p><hr/><h3>输出格式</h3><p><p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">文件的第一行为一个单词，&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Yes</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;或&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">No</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;&mdash;&mdash;如果存在符合要求的设计方案，则为&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">Yes</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;，否则为&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">No</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">如果第一行是&ldquo;</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">No</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;，则文件结束，否则&mdash;&mdash;</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第二行只有一个非负整数</span><i><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">p</font></span></i><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，表示最少需要的门电路数目。下面</span><i><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">p</font></span></i><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行分别给出每个门电路在电路中的连接情况的描述。每行有四个以空格隔开的正整数：</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">S K A B</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，其中</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">S</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示该门电路的编号（所有用到的门电路按</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">5~<i>p</i>+4</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">编号，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1~4</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的编号用来表示四个输入端）；</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">K</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示该元件的种类编号（按照输入文件中的顺序由</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1~</font><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" path="m@4@5l@4@11@9@11@9@5xe" stroked="f" o:preferrelative="t" filled="f"><font face="Times New Roman"> <v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path gradientshapeok="t" o:connecttype="rect" o:extrusionok="f"></v:path><o:lock v:ext="edit" aspectratio="t"></o:lock></font></v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" o:ole="" style="width: 9.75pt; height: 11.25pt"><v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.wmz" o:title=""></v:imagedata></v:shape></span></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">编号）；</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">A</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">B</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">分别表示接入该元件的两个输入端的门电路或译码电路输入端的编号（其中，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">A&lt;S</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">B&lt;S</font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">）。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0cm 0cm 0pt; text-indent: 24pt; text-align: left; mso-char-indent-count: 2.0"><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">最后一行有四个正整数，表示组成的译码电路的四个输出端分别所接的元件的编号（在</span><span lang="EN-US" style="font-size: 12pt"><font face="Times New Roman">1~<i>p</i></font></span><span style="font-size: 12pt; font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">之间）。</span><span lang="EN-US" style="font-size: 12pt"><o:p></o:p></span></p>
<p></p></p><hr/><h3>样例输入</h3><pre>1
5 0 1 0
0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0
0 1 0 0 1 1 0 0
1 1 0 0 0 1 0 0
0 0 1 0 0 1 1 0
1 0 1 0 1 1 1 0
0 1 1 0 1 0 1 0
1 1 1 0 0 0 1 0
0 0 0 1 0 0 1 1
1 0 0 1 1 0 1 1
0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1
0 0 1 1 0 1 0 1
1 0 1 1 1 1 0 1
0 1 1 1 1 0 0 1
1 1 1 1 0 0 0 1
</pre><hr/><h3>样例输出</h3><pre>Yes
3
5 1 2 1
6 1 3 2
7 1 4 3
5 6 7 4
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2543" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2543" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>